//随机生成数组的函数
function creatArray(length){
    let array = new Array(length)
    for(let i = 0, len = length; i < len; i++){
        array[i] = Math.floor(Math.random()*length)
    }
    return array
}
let myArray = creatArray(10000)

let arr = [1,2,6,7,1,0,2,54,63,9]

function mergeSort(arr){
    if(arr.length > 1){
        let middle = Math.floor(arr.length/2) //取中间数组的下标
        let left = mergeSort(arr.slice(0,middle)) //左边一直分到不能二分为止
        let right = mergeSort(arr.slice(middle,arr.length)) //右边一直分到不能二分为止
        arr = merge(left,right)
    }
    return arr
}

function merge(left,right){ //按顺序拼接数组的函数
    let i = 0
    let j = 0
    let result = []
    while(i < left.length && j < right.length){ //当左边的数组内还有元素并且右边的数组也有元素时
        result.push((left[i] < right[j]) ? left[i++] : right[j++]) //左边数组的每一项和右边数组的每一项进行比较大小，小的放进result
        //对比到最后，一定是左边数组的每一项都进了result，纵使右边数组有几项小于左边数组，右边数组小的那几项也会跟着进result，
        //然后右边数组比左边数组大的就会 全部剩下 成为 新的右边数组
    }
    //这时候只需要将结果result数组去拼接剩下的数组即可
    return result.concat(i < left.length ? left.slice(i) : right.slice(j)) //将结果数组result直接拼接剩余的数组项，并返回拼接后结果数组
    //如果i（左边数组下标）还没有达到左边数组最后一个下标，说明剩下的元素是左边数组的，否则剩下的就是右边数组的元素
}

mergeSort(arr) //注意这里是返回新的数组，不对原数组进行修改




